We consider the fundamental problem of solving quadratic systems of equationsin $n$ variables, where $y_i = |\langle \boldsymbol{a}_i, \boldsymbol{x}\rangle|^2$, $i = 1, \ldots, m$ and $\boldsymbol{x} \in \mathbb{R}^n$ isunknown. We propose a novel method, which starting with an initial guesscomputed by means of a spectral method, proceeds by minimizing a nonconvexfunctional as in the Wirtinger flow approach. There are several keydistinguishing features, most notably, a distinct objective functional andnovel update rules, which operate in an adaptive fashion and drop terms bearingtoo much influence on the search direction. These careful selection rulesprovide a tighter initial guess, better descent directions, and thus enhancedpractical performance. On the theoretical side, we prove that for certainunstructured models of quadratic systems, our algorithms return the correctsolution in linear time, i.e. in time proportional to reading the data$\{\boldsymbol{a}_i\}$ and $\{y_i\}$ as soon as the ratio $m/n$ between thenumber of equations and unknowns exceeds a fixed numerical constant. We extendthe theory to deal with noisy systems in which we only have $y_i \approx|\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$ and prove that ouralgorithms achieve a statistical accuracy, which is nearly un-improvable. Wecomplement our theoretical study with numerical examples showing that solvingrandom quadratic systems is both computationally and statistically not muchharder than solving linear systems of the same size---hence the title of thispaper. For instance, we demonstrate empirically that the computational cost ofour algorithm is about four times that of solving a least-squares problem ofthe same size.
展开▼
